This application relates to the field of microprocessors and microprocessor systems, and specifically to techniques for allocating resources between competing resource requests. Resources in microprocessors and microprocessor systems are often constrained. For example, a system memory interface is constrained by the bandwidth of the system memory and the memory bus. Similarly, a thread or task scheduler is constrained by the maximum number of threads capable of being processed simultaneously by a microprocessor. In another example, a cache memory controller may be configured to service critical requests first and be constrained by the number of spare cache access cycles available for non-critical cache accesses.
Multiple resource requests can come from the same entity or a different entity within a microprocessor or microprocessor system. For example, a single processor core may issue multiple requests for data from system memory to a system memory interface. In another example, multiple processor cores operating independently within a microprocessor may issue multiple requests for data from system memory to a system memory interface.
Regardless of the source or sources of the resource requests, the entity receiving the requests (such as a communications bus controller, a system memory interface, a cache memory controller, a thread or task scheduler, or any other resource in a microprocessor or microprocessor system) must efficiently allocate resources (such as cache or system memory accesses, data communications bus accesses, and processing resources) between multiple resource requests. For example, a cache memory controller within a microprocessor may receive multiple requests to write data in a cache memory. The cache memory controller must determine which pending or outstanding requests to service immediately and which to defer for a later time.
There are many different arbitration schemes previously used to allocate resources. One of the simplest is a first-come, first-served arbitration scheme. In this scheme, resource requests are processed in the order they are received. A fixed priority scheme assigns a static priority to different requests and services the requests in order of priority. Although this scheme is simple to implement, it can allow one requester to monopolize resources. This leads to resource starvation for the other requesters. A round-robin arbitration scheme assigns resources to each requester in equal portions and in order. Although this prevents resource starvation, it is also less efficient as resources may be allocated to requester even if they do not have any pending requests. Additionally, round-robin arbitration does not allow pending requests to be prioritized.
Other arbitration schemes can use weighting or other prioritization techniques to improve efficiency. However, these schemes are complicated. In many microprocessor and microprocessor systems, the arbitration scheme is implemented using logic circuits and other hardware. The complexity of these other arbitration schemes often requires substantial amounts of logic circuits to implement with hardware, making these schemes unsuitable for microprocessors and microprocessor systems, where device area is scarce.
It is therefore desirable for an arbitration scheme to provide improved resource utilization, eliminate resource starvation, and allow for request prioritization. It is further desirable for the arbitration scheme to be implemented in hardware using minimal additional logic circuits as compared with first-come, first-served and round-robin arbitration schemes. It is also desirable for the arbitration scheme to be adaptable to a wide variety of applications within microprocessors and microprocessor systems.